package leetcode.p363;

import java.util.Set;
import java.util.TreeSet;

/**
 * @author: trtan
 * @create: 2021-04-22 10:18
 * @description:
 **/
public class MaxRectangleNoLargerThanK {
    public static void main(String[] args) {
        int[][] matrix = {{2,2,-1}};
        int k = 4;
        System.out.println(new MaxRectangleNoLargerThanK().maxSumSubmatrix(matrix, k));
    }

    void initPreSum(int[][] preSum, int[][] matrix, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                preSum[i][j] = matrix[i][j];
                if (i != 0 && j != 0) {
                    preSum[i][j] -= preSum[i - 1][j - 1];
                }
                if (i != 0) {
                    preSum[i][j] += preSum[i - 1][j];
                }
                if (j != 0) {
                    preSum[i][j] += preSum[i][j - 1];
                }
            }
        }
    }
    int getValue(int[][] preSum, int top, int bottom, int right) {
        int result = preSum[bottom][right];
        if (top > 0) {
            result -= preSum[top - 1][right];
        }
        return result;
    }
    /**
     * @author trtan
     * @date 2021/4/22 10:39
     * description:
     * @param matrix
     * @param k
     * @return int
     * now - floor <= k;
     * -floor <= k - now;
     * floor >= now - k;
     */
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] preSum = new int[n][m];
        int maxResult = Integer.MIN_VALUE;
        initPreSum(preSum, matrix, n, m);
        TreeSet<Integer> sortSet = new TreeSet<>();
        // 下边界
        for (int bottom = 0; bottom < n; bottom++) {
            // 上边界
            for (int top = 0; top <= bottom; top++) {
                sortSet.clear();
                sortSet.add(0);
                //右边界
                for (int right = 0; right < m; right++) {
                    int now = getValue(preSum, top, bottom, right);
                    Integer floor = sortSet.ceiling(now - k);
                    if (floor == null) {
                        floor = 0;
                    }
                    if (now - floor <= k) {
                        maxResult = Math.max(now - floor, maxResult);
                    }
                    sortSet.add(now);
                }
            }
        }
        return maxResult;
    }

}
